The invention relates generally to transportation networks, and relates more particularly to the incorporation of dynamic data in transportation network calculations.
FIG. 1 is a schematic diagram illustrating a typical large-area transportation network 100. The transportation network 100 comprises a plurality of urban metropolitan areas 1021–102N (hereinafter collectively referred to as “metropolitan areas 102), towns 1041–104N (hereinafter collectively referred to as “towns 104”) and inter-urban and/or rural areas (generally designated 106) situated between the metropolitan areas 102 and towns 104. The metropolitan areas 102, towns 104 and inter-urban/rural areas 106 that comprise the transportation network 100 may span a large geographical area (e.g., comprising a plurality of cities, states, regions or countries).
When traveling between locations in a transportation network, it is typically desirable to identify a shortest path, or best (e.g., fastest) route, to travel from an origin to a destination. Conventional applications such as internet mapping and vehicle navigation systems typically compute this best route based on static, non-state-dependent data about links in the transportation network (e.g., speed limits, numbers of lanes, average loads).
A problem with this approach is that dynamic, state-dependent data that may influence travel time (e.g., current traffic conditions or other environmental factors) is not accounted for. Thus, a computed route may not, in fact, be the best route at a given time. Although some methods currently exist that do account for current traffic states, these existing methods are computationally intensive and limited to small or moderately-sized geographic areas. They are thus difficult to scale to larger, geographically heterogeneous transportation networks (such as the transportation network 100).
Thus, there is a need for a method and an apparatus for end-to-end travel time estimation using dynamic traffic data.